
\subsection{Das Lamport-Diffie Einmalverfahren \buchmann{13.7}}

Das Lamport-Diffie Einmalverfahren (Lamport-Diffie one-time signature scheme; kurz LD-OTS) wurde 1979, gleichzeitig mit RSA, veröffentlicht.
Im Gegensatz zu RSA beruht die Sicherheit von LD-OTS nicht auf der Schwierigkeit natürliche Zahlen in ihre Primfaktoren zu zerlegen oder 
diskrete Logarithmen in geeigneten Gruppen zu berechnen. LD-OTS ist damit nicht von der Problematik, dass Quantencomputer diese Probleme
effizient lösen können, betroffen.
 
 Das LD-OTS verwendet die folgende Einwegfunktion $H$, wobei $n \in \mathbb{N}$ der Sicherheitsparameter von LD-OTS ist.
 
 $$H: \lbrace 0,1 \rbrace ^n \rightarrow \lbrace 0,1\rbrace^n, n \in \mathbb{N}$$



% Das Thema Sicherheit wird in Abschnitt \ref{lamport:sicherheit} erläutert.
Die Einweg-Eigenschaft dieser Funktion ist die Sicherheitsvoraussetzung von LD-OTS. Diese Voraussetzung ist minimal, da jedes heute verwendete
Signaturverfahren eine kryptographisch sichere Hashfunktion benutzt.

\subsubsection{Schlüsselerzeugung \buchmann{13.7.1}}

Der LD-OTS-Signaturschlüssel ist eine Matrix, die aus Vektoren der Länge $n$ gebildet wird.
Ein Vektor wird gegeben durch $x(i,n), i \in \lbrace 0,1 \rbrace$. Die Matrix ergibt sich
wie folgt

$$ x = (x(0,1),x(1,1),x(0,2),x(1,2),\ldots,x(0,n),x(1,n)) \in \lbrace 0,1 \rbrace^{n\times 2n}  $$

Der zugehörige Verifikationsschlüssel ist ebenfalls ein String

\begin{align*}
 y &= (y(0,1),y(1,1),y(0,2),y(1,2),\ldots,y(0,n),y(1,n)) \\
&= (H(x(0,1)),H(x(1,1)),H(x(0,2)),H(x(1,2)),\ldots,H(x(0,n)),H(x(1,n))) \in \lbrace 0,1 \rbrace^{n\times 2n}
\end{align*}

\subsubsection{Erzeugung der Signatur \buchmann{13.7.2}}

Die Signatur eines Dokumentes $d=(d_1,\ldots,d_n) \in \lbrace 0,1 \rbrace ^n $ ist die Folge

\begin{align*}
 s &= (s_1,\ldots,s_n) \\
&= (x(d_1,1),\ldots,x(d_n,n))
\end{align*}

Mittels des Bitstrings, des zu signierenden Dokuments, wird entschieden welche Bitstring-Vektoren aus dem
Signaturschlüssel die Signatur ergeben. Die Signatur enthält damit einen Teil des geheimen Signaturschlüssels.
In der Praxis wird das zu signierende Dokument mittels einer Hashfunktion auf die Größe $n$ abgebildet.

\subsubsection{Verifikation der Signatur \buchmann{13.7.3}}

Der Verifizierer kennt die Einwegfunktion $H$, den öffentlichen Verifikationsschlüssel $y$, das Dokument $d$ und die Signatur $s$.
Die Signatur akzeptiert er, wenn
\begin{align*}
 (H(s_1),\ldots,H(s_n)) &= (y(d_1,1),\ldots,y(d_n,n)) \\
 &= (H(x(d_1,1)),\ldots,H(x(d_n,n)))
\end{align*}


\emph{Beispiel 13.7.1 abgeändert}

Der Sicherheitsparameter ist $n = 3$. 

Das Dokument ist  $d = (001)$. 

Die vereinfachte Einwegfunktion $H$ bildet $(d_1,d_2,d_3)$ auf $(d_3,d_2,d_1)$ ab. (Bsp: $H( \begin{pmatrix}0\\1\\1 \end{pmatrix})= \begin{pmatrix}1\\1\\0 \end{pmatrix},H( \begin{pmatrix}0\\0\\1 \end{pmatrix})= \begin{pmatrix}1\\0\\0 \end{pmatrix}$)

Der Signierschlüssel sei
 
$$(x(0,1),x(1,1),x(0,2),x(1,2),x(0,3),x(1,3)) = \begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1  \end{pmatrix}$$ 

Damit ergibt sich für den Verifikationsschlüssel (Jeden Bitstring-Vektor des Signierschlüssels hashen)

\begin{align*}
(y(0,1),y(1,1),y(0,2),y(1,2),y(0,3),y(1,3)) &= (H(x(0,1)),H(x(1,1)),H(x(0,2)),H(x(1,2)),H(x(0,3)),H(x(1,3))) \\
&= \begin{pmatrix}    1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}
\end{align*}

Die Signatur, von $d=(001)$, berechnet sich wie folgt (Bitstring-Vektoren abhängig vom Bitstring des Dokuments wählen)

\begin{align*}
s = (s_1,s_2,s_3) &= (x(d_1,1),x(d_2,2),x(d_3,3)) \\
&= (x(0,1),x(0,2),x(1,3)) \\
&= \begin{pmatrix}    0 & 1 & 1 \\ 1 & 1 & 0  \\ 1 & 0 & 1 \end{pmatrix}
\end{align*}

Um diese Signatur zu verifizieren, berechnet der Verifizierer (Jeden Bitstring-Vektor der Signatur hashen)

$$(H(s_1),H(s_2),H(s_3))=\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0  \\ 0 & 1 & 1 \end{pmatrix}$$

und prüft danach, ob

\begin{align*}
(H(s_1),H(s_2),H(s_3))&=(y(d_1,1),y(d_2,2),y(d_2,2),)\\
&=(y(0,1),y(0,2),y(1,2),)
\end{align*}

\newpage

\subsection{Das Merkle-Verfahren \buchmann{13.8}}

LD-OTS bietet einen hohen Sicherheitsgrad, ist in der Praxis aber unpraktikabel. Da jede Signatur ein neues Schlüsselpaar benötigt.
Das Merkle-Signaturverfahren löst dieses Problem, mittels eines binären Hashbaums. Somit können viele Einmal-Verifikationsschlüssel
auf einen öffentlichen zurückgeführt werden. Das Merkle Verfahren ermöglicht es also viele Signaturen mit Hilfe eines
Einmal-Signaturverfahren zu erzeugen, die mit einem öffentlichen Schlüssel verifizierbar sind.  

\subsubsection{Initialisierung \buchmann{13.8.1}}

Für das Merkle-Verfahren benötigen wir eine Hashfunktion

$$H:\lbrace 0,1 \rbrace^* \rightarrow \lbrace 0,1 \rbrace^n$$

und ein Einmal-Signaturverfahren. Wir wählen hier das Lamport-Diffie-Verfahren. Als nächstes wird festgelegt,
wie viele Signaturen mit einem einzigen öffentlichen Schlüssel verifizierbar sein sollen. Die Anzahl
der verifizierbaren Signaturen ist $N = 2^h$ wobei $h \in \mathbb{N} $.

\emph{Beispiel 13.8.1 abgeändert}

Unsere Hashfunktion arbeitet wie folgt: Der Hashwert sind die letzten drei Bits der Binärdarstellung der Quersumme
 der Dezimalzahl, deren Hashwert berechnet werden soll. Ist die Binärdarstellung zu kurz, werden führende Nullen
 ergänzt. 
 
 Vorgehensweise zum Hashen:
 
\begin{enumerate}
\item Zahl dezimal darstellen. 
\item Quersumme bilden
\item  Binärdarstellung der Quersumme bilden.
\item Die letzten drei Bits stellen den Hashwert dar. (ggf führende Nullen ergänzen)
\end{enumerate}
 
\textbf{Konkretes Beispiel:}
 
Wir wollen den Hashwert von $d = 10000000000010$ berechnen.

\begin{enumerate}
\item Dezimaldarstellung: $2^{13}+2^1 = 8194$
\item Quersumme: $8+1+9+4 = 22$
\item  Binärdarstellung der Quersumme: $22 = 2^4+2^2+2^1 \rightarrow 10110$
\item Letzten drei Bits: 110
\end{enumerate}

Der Hashwert von $d = 10000000000010$ ist also $H(d) = 110$

\newpage
\subsubsection{Schlüsselerzeugung \buchmann{13.8.2}}

Zum Signieren wählt man $N$ Schlüsselpaare $(x_i,y_i)$ ($0 \leq i < N$), des verwendeten Einmal-Signaturverfahrens.
Dabei ist $x_i$ und $y_i$ jeweils ein Signierschlüssel und Verifikationsschlüsselpaar.
Im Falle des Lamport-Diffie Einmalverfahren besteht jedes $x_i$ aus der Matrix $(x(0,1),x(1,1),x(0,2),\ldots)$ und 
jedes $y_i$ aus der Matrix $(H(x(0,1)),\ldots)$.  Als nächstes wird der binäre Merkle-Hashbaum erzeugt. Es
wird mit dem Blättern begonnen, sie enthalten die gehashten Verifikationsschlüssel $H(y_i)$ ($0 \leq i < N$). Die nächsten Schritte bauen
den Baum weiter aus bis zur Wurzel. Jeder Knoten des Baums entsteht aus den beiden darunter liegenden Knoten und wird gebildet indem 
das linke Kind ($k_l$) mit dem rechten ($k_r$) verkettet wird und anschließend gehasht. Der öffentliche Schlüssel ist die Baumwurzel $R$.
Die Signierschlüssel sind die Folge ($x_0,\ldots,x_{N-1}$).

\emph{Beispiel 13.8.2 abgeändert}

Wir wählen vier Paare $(x_i,y_i)$ ($0 \leq i < 4$), die jeweils aus sechs Bitstrings der Länge 3 bestehen. Die Knoten des Baumes werden
mit $K_{i,j}$  bezeichnet, dabei ist $i$ die Position (von links) und $j$ die Tiefe im Baum. Die Blätter des Baumes sind:

$$
K_{0,2} = H(y_0) = 110,K_{1,2} = H(y_1) = 001,K_{2,2}  = H(y_2) = 010,K_{3,2} = H(y_3) = 101
$$

Zur Berechnung der Knoten darüber gehen wir vor wie folgt:

\begin{align*}
K_{0,1} &= H(K_{0,2} \circ K_{1,2}) = H(110001) = 101 \\
K_{1,1} &= H(K_{2,2} \circ K_{3,2}) = H(010101) = 011
\end{align*}

Analog dazu wird die Wurzel (der öffentliche Verifikationsschlüssel) berechnet:

$$
R = K_{0,0} = H(K_{0,1} \circ K_{1,1}) = H(101011) = 111
$$

\begin{figure}[htbp]
	\centering
		\includegraphics[width=0.6\textwidth]{ex5_signature/misc/hashbaeume_1.pdf}
	\caption[baum1]{Merkle-Hashbaum der Höhe $h = 2$}
	\label{diagramm}
\end{figure}
\newpage
\subsubsection{Schlüsselerzeugung \buchmann{13.8.3}}

Wird ein Dokument $d$ signiert, benutzt der Signierer dazu einen Zähler $i$, der auf den ersten noch nicht verwendeten 
Signierschlüssel zeigt. Der Wert $i$ ist der Zustand des Signierers, dass Merkle-Verfahren ist "`stateful"'. Initial ist 
$i = 0$.

Der Signierer berechnet mittels eines $x_i$, abhängig von $i$, die Signatur des Dokuments $d$. Anschließend wird ein
Authentisierungspfad berechnet. Dieser ermöglicht es dem Verifizierer die Gültigkeit des mitgesendeten Verifikationsschlüssels 
$y_i$ auf die Gültigkeit des öffentlichen Schlüssels $R$ zurückzuführen. Dieser Pfad beinhaltet die Partner, von $y_i$ ausgehend,
die nötig sind um alle Knoten bis zur Wurzel des Baumes zu berechnen. Die Partner werden mit $a_h$ $h \geq i \geq 1$ bezeichnet.

Die Signatur von d ist wie folgt:

$$
S = (i,y_i,s,(a_h,\ldots,a_1))
$$

Nachdem die Signatur erstellt wurde, wird der Zähler $i$ um eins erhöht.

\emph{Beispiel 13.8.3 abgeändert}

Fortführung von Beispiel 13.8.2:

Signiert wird das Dokument $d$. Der Zähler $i$ ist 3. Es wird demnach der Signierschlüssel $x_3$ verwendet. Die Einmal-Signatur bezeichnen wir mit $s$. Wir bestimmen den Pfad vom Blatt
 $K_{3,2}$ zu $R$, dieser lautet $K_{3,2},K_{1,1},K_{0,0}$. Damit ergibt sich der Authentisierungspfad: $(a_2, a_1)$.
 Die vollständige Signatur ist also $(3,y_3,s,(a_2,a_1))$.

\begin{figure}[htbp]
	\centering
		\includegraphics[width=0.6\textwidth]{ex5_signature/misc/hashbaeume_2.pdf}
	\caption[baum2]{Authentisierungspfad für das 4. Blatt ($y_2$).}
	\label{diagramm}
\end{figure}


\newpage
\subsubsection{Verifikation \buchmann{13.8.4}}

Der Verifizierer erhält das Dokument $d$ und die Signatur $(i,y_i,s,(a_h,\ldots,a_1))$. Zunächst verifiziert er die Signatur $s$
unter Verwendung von $y_i$. Schlägt diese Verifikation fehl, wird die Signatur zurückgewiesen. Anderenfalls überprüft der Verifizierer
die Gültigkeit des Verifikationsschlüssels $y_i$. Dazu verwendet er die Zahl $i$, den Authentisierungspfad $(a_h,\ldots,a_1)$, $y_i$ und $R$.
Zuerst wird $H(y_i)=b_h$ berechnet. Außerdem ist bekannt, dass $b_h$ und der Knoten $a_h$ denselben Vater haben. Es ist aber nicht bekannt
ob $a_h$ der linke oder der rechte Partner von $b_h$ ist. Dies kann mittels $i$ bestimmt werden. Wandelt man $i$ in seine Binärdarstellung
und arbeitet sie "`von vorne"' ab, bedeutet eine "`1"' "`nach rechts"' und eine "`0"' nach links (Beispiel: $000 \rightarrow$ nur links abbiegen, führt
zum Blatt 0; $111\rightarrow$ nur rechts abbiegen, führt zum Blatt 3). Arbeitet man die Binärdarstellung von hinten her ab,
 bedeutet eine daher eine "`1"' dass $a_h$ der linke Partner von $b_h$ ist, bei einer "`0"' umgekehrt.

\emph{Beispiel 13.8.4 abgeändert}

Dem Verifizierer ist das Dokument $d$, die Signatur $(2,y_2,s,(a_2=101,a_1=101))$ und $R = 111$ bekannt.
Er verifiziert die Signatur mit dem Verifikationsschlüssel $y_2$ und ist erfolgreich. Nun muss er den
Verifikationsschlüssel validieren. Dazu bestimmt er die Binärentwicklung von $2$ sie ist $10$.
Jetzt berechnet er den Hashwert von $H(y_2) = b_2 = 010$. Nun wird die Binärentwicklung von $i$ betrachtet, das 
letzte Bit ist 0 das heißt $a_2$ ist der rechte Partner von $b_2$. Damit ist $K_{1,1}=H(b_2 \circ a_2)=H(010101)=011$.
Im nächsten Schritt nehmen wir das nächste Bit von $i$ und wiederholen den Vorgang. Das Bit ist hier 1, demnach ist 
$a_1$ der linke Partner von $K_{1,1}$ und es gilt: $K_{0,0} = H(a_1 \circ K_{1,1}) = H(101011) = 111$.
Dieser Wert stimmt mit $R$ überein, damit ist $y_2$ verifiziert
und die Signatur wird akzeptiert.

\begin{figure}[htbp]
	\centering
		\includegraphics[width=0.6\textwidth]{ex5_signature/misc/hashbaeume_3.pdf}
	\caption[baum3]{Validierung des Verifikationsschlüssels $y_2$.}
	\label{diagramm}
\end{figure}
 
